package dataStructure.kmp;

import java.util.Arrays;

/**
 * @author lhn
 * @date 2024-09-10 16:16
 */

public class KMPDemo {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";

//        int[] matchingTable = obtainPartialMatchingTable("AAAB");
        int[] matchingTable = obtainPartialMatchingTable(str2);
        System.out.println(Arrays.toString(matchingTable));

        System.out.println(
                kmpMatch(str1, str2, matchingTable)
        );

    }

    /**
    *
     * @param str1 待匹配字符串
     * @param str2 子串
     * @param matchingTable 部分匹配表
     * @return int
    */
    public static int kmpMatch(String str1, String str2, int[] matchingTable) {
        for (int i = 0, j = 0; i < str1.length(); i++) {

            // 如果j大于0，并且字符不相等，则j回退到之前匹配最长的长度
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = matchingTable[j - 1];
            }

            if (str1.charAt(i) == str2.charAt(j)) {
                j ++;
            }

            if (j == str2.length()) {
                return i - j + 1;   // 返回匹配的位置
            }
        }

        return -1;
    }

    /**
    * 获取部分匹配表
     * @param str
     * @return int[]
    */
    public static int[] obtainPartialMatchingTable (String str) {
        int[] matchTable = new int[str.length()];
        matchTable[0] = 0;  // 默认为0

        //  i取后缀子串(不包含第个一字母)，j取前缀子串(不包含最后一个字母)
        for (int i = 1, j = 0; i < str.length(); i++) {

            char char_1 = str.charAt(i);
            char char_2 = str.charAt(j);

            // 如果j大于0，并且字符不相等，则j回退到之前匹配最长的长度
            while (j > 0 && char_1 != char_2) {
                j = matchTable[j - 1];
            }

            // 如果字符相等，则j+1，继续比较看能匹配上几位
            if (char_1 == char_2) {
                j ++ ;
            }
            matchTable[i] = j;
        }
        return matchTable;
    }
}
